\subsection{Computable functions and sets}
\begin{remark}
	A lot of computations require the use of scratch space, and we want to reduce the mathematical information related to this scratch space.
	In the following definition, only register zero is considered real output; all other registers are considered scratch space.
\end{remark}
\begin{definition}
	Let \( M \) be a register machine, and let \( k \in \mathbb N \).
	Then we define \( f_{M,k} \colon \mathbb W^k \rightharpoonup \mathbb W \) by \( f_{M,k}(\vb w) \uparrow \) when \( M \) does not halt on input \( \vb w \), and \( f_{M,k}(\vb w) = v_0 \) when \( M \) halts on input \( \vb w \) with halting register content \( \vb v \).
\end{definition}
Note that if \( M, M' \) are strongly equivalent, \( f_{M,k} = f_{M',k} \) for all \( k \).
The converse does not hold.
For the special case of \( k = 1 \), we also write \( W_M = \dom f_{M,1} \).
\begin{definition}
	A partial function \( f \colon \mathbb W^k \rightharpoonup \mathbb W \) is called \emph{computable} if there is a register machine \( M \) such that \( f = f_{M,k} \).
\end{definition}
\begin{remark}
	There are only countably many computable functions, because there are only countably many register machines up to strong equivalence.
	For each computable function \( f \), there are infinitely many register machines \( M \) such that \( f = f_{M,k} \), since any register machine has infinitely many other strongly equivalent register machines.
	Due to the concatenation lemma and the case distinction lemma, computable functions are closed under concatenation and case distinction.
\end{remark}
\begin{example}
	The identity function on \( \mathbb W \) is computable.
	Consider \( c \colon \mathbb W^k \to \mathbb W \) is given by \( c(\vb w) = v \) for a fixed \( v \).
	The operation `replace the content of register \( 0 \) with \( v \)' is performable on a register machine, so \( c \) is computable.
	The projection \( \pi_i \colon \mathbb W^k \to \mathbb W \) given by \( \pi_i(\vb w) = w_i \) is computable since the operation `replace the content of register \( 0 \) with register \( i \)' can be performed on a register machine by emptying register \( 0 \) and then moving the content of register \( i \) to register \( 0 \).
\end{example}
\begin{definition}
	Let \( X \subseteq \mathbb W^k \).
	We say that a total function \( f \colon \mathbb W^k \to \mathbb W \) is \emph{a characteristic function of \( X \)} if \( f(\vb w) \neq \varepsilon \) if and only if \( \vb w \in X \).
	Let \( a \in \Sigma \).
	We say that \( f \) is \emph{the characteristic function of \( X \)} if \( f(\vb w) = a \) if \( \vb w \in X \) and \( f(\vb w) = \varepsilon \) otherwise.
\end{definition}
We use the notation \( \chi_X \) for the characteristic function.
\begin{definition}
	A set \( X \subseteq \mathbb W^k \) is \emph{computable} if the characteristic function \( \chi_X \) of \( X \) is computable.
\end{definition}
Note that a language is a set of words, so we can now reason about computability of languages.
\begin{definition}
	Let \( X \subseteq \mathbb W^k \).
	A partial function \( f \colon \mathbb W^k \rightharpoonup \mathbb W \) is called \emph{a pseudocharacteristic function of \( X \)} if \( \dom f = X \).
	\( f \) is called \emph{the pseudocharacteristic function of \( X \)} if \( f(\vb w) = a \) if \( \vb w \in X \), and undefined otherwise.
\end{definition}
We use the notation \( \psi_X \) for the pseudocharacteristic function.
\begin{definition}
	A set \( X \subseteq \mathbb W^k \) is \emph{computably enumerable} if the pseudocharacteristic function \( \psi_X \) is computable.
\end{definition}
\begin{remark}
	We will show that every computable set is computably enumerable, but the converse does not hold.
	We will also show that the computably enumerable sets are exactly the type 0 languages (those languages that have grammars), and that the class of computable languages is properly contained between type 1 and type 0.
\end{remark}

\subsection{Computability of languages}
\begin{proposition}
	Let \( X \subseteq \mathbb W^k \).
	Then:
	\begin{enumerate}
		\item \( X \) is computable if and only if \( X^c \) is computable.
		\item \( X \) is computably enumerable if and only if there exists a register machine \( M \) such that \( X = \dom f_{M,k} \).
		\item If \( X \) is computable, then \( X \) is computably enumerable.
	\end{enumerate}
\end{proposition}
\begin{proof}
	To simplify notation we consider the case \( k = 1 \).
	Note that if \( g \) and \( h \) are computable, then by the case distinction lemma, so is \( f \) defined by \( f(w) = g(w) \) if \( w \neq \varepsilon \), and \( f(w) = h(w) \) if \( w = \varepsilon \).

	For the first part, consider the computable function \( f_1 \) given by \( g(w) = \varepsilon \) and \( h(w) = a \).
	Then \( f_1 \circ \chi_X = \chi_{X^c} \), \( f_1 \circ \chi_{X^c} = \chi_X \).

	Now consider \( f_2 \) given by \( g(w) = a \) and \( h(w) = \varepsilon \).
	If \( X = \dom f \), then \( \psi_X = f_2 \circ f \).

	Finally, consider \( f_3 \) given by \( g(w) = a \) and \( h(w) \uparrow \).
	Then \( \psi_X = f_3 \circ \chi_X \).
\end{proof}
\begin{theorem}
	Every regular language is computable.
\end{theorem}
\begin{proof}
	Let \( L \) be such a regular language.
	Let \( D = (\Sigma, Q, \delta, q_0, F) \) be a deterministic automaton such that \( L = \mathcal L(D) \).
	The first step in our program is to reverse the content of register 0 into register 1, because register machines read words in the opposite order of deterministic automata.
	For each \( q \in Q \), the register machine will have a set of states \( Q_q \) that indicate that we are currently mimicking \( D \) in state \( q \).
	We will now move into the state set \( Q_{q_0} \).

	When moving into each state set \( Q_q \), our program will read the final letter of register 1.
	If there are no letters in register 1, go to a fixed accepting state if \( q \in F \) and the non-accepting state if \( q \not\in F \).
	Otherwise, let \( b \) be the last letter in register 1.
	Remove \( b \) from register 1, and go to state set \( Q_{\delta(q,b)} \).
	We implicitly repeat this step, since we have now transitioned into a state set.

	If the machine is in the given accepting state, we empty register 0, add \( a \) to register 0, and then halt.
	If the machine is in the non-accepting state, we empty register 0, and then halt.
\end{proof}

\subsection{The shortlex ordering}
We wish to create an order \( < \) on \( \mathbb W \) such that \( (\mathbb N, <) \) is order-isomorphic to \( (\mathbb W, <) \).
We first fix an arbitrary total order \( < \) on \( \Sigma \).
\begin{definition}
	The \emph{shortlex ordering} on \( \mathbb W \) given by an ordering of \( \Sigma \) is given by \( w < v \) when
	\begin{enumerate}
		\item \( \abs{w} < \abs{v} \); or
		\item \( \abs{w} = \abs{v} \) but \( w \neq v \), and for the least \( m \) such that the \( m \)th characters differ, the \( m \)th character of \( w \) is less than the \( m \)th character of \( v \).
	\end{enumerate}
\end{definition}
This ordering first checks length, then the lexicographic ordering.
This is a total ordering on \( \mathbb W \); it is irreflexive, transitive, and trichotomous.
The empty word is the least element.
\begin{example}
	Let \( \Sigma = \qty{0,1} \), and fix \( 0 < 1 \).
	Then an initial segment of the ordering is
	\[ \varepsilon, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111, 0000, \dots \]
	We can identify each word with a natural number, given by its index in this sequence, counting from zero.
	There are \( 2^k \) words of length \( k \), so the index of the natural number associated to the word \( 0^k \) is exactly \( 2^k - 1 \).

	We can naturally extend the operations of addition and multiplication on the set of words by acting on the index of the word in this ordering.
	For example, \( 10 + 01 = 010 \), because the associated index of \( 10 \) is \( 5 \), the index of \( 01 \) is \( 4 \), and the index of \( 010 \) is \( 9 \).
	This gives \( \mathbb W \) the structure of a commutative semiring.
\end{example}
\begin{theorem}
	The shortlex ordering has the same order type as \( \mathbb N \).
	We write \( (\mathbb N, <) \cong (\mathbb W, <) \).
\end{theorem}
\begin{proof}
	For a fixed \( w \), the set \( \qty{v \mid v < w} \) is finite.
	Therefore, the function \( \# \colon \mathbb W \to \mathbb N \) given by \( \#(w) = \abs{\qty{v \mid v < w}} \) is well-defined and is an order isomorphism.
\end{proof}
\begin{theorem}
	The set \( \qty{(v,w) \mid v < w} \) is computable.
	The \emph{successor function} \( s \colon \mathbb W \to \mathbb W \) with \( \#(s(w)) = \#(w)+1 \) is computable.
\end{theorem}
\begin{proof}
	The question to determine the ordering of \( \abs{w_i} \) and \( \abs{w_j} \) can be answered by a register machine by copying \( i, j \) into empty registers and repeatedly removing letters until one or both is empty.
	If they have the same length, we again copy \( i, j \) into empty registers in the reverse order, and check and remove each letter until a difference is found.

	To compute \( s(w) \) for a word \( w \), we find the last letter in \( w \) that is not the largest letter in the ordering.
	Replace this letter with the next letter in the ordering, and replace all subequent letters with the least letter in the ordering.
	If all \( k \) letters are the greatest letter, output the least letter \( (k + 1) \)-many times.
\end{proof}

\subsection{Church's recursive functions}
The class of recursive functions is defined inductively.
\begin{definition}
	The \emph{basic functions} are
	\begin{align*}
		\pi_{k,i} &\colon \mathbb W^k \to \mathbb W \\
		c_{k,\varepsilon} &\colon \mathbb W^k \to \mathbb W \\
		s &\colon \mathbb W \to \mathbb W
	\end{align*}
	where \( \pi_{k,i}(\vb w) = w_i \), \( c_{k,\varepsilon}(\vb w) = \varepsilon \), and \( \# s(w) = \# w + 1 \).
\end{definition}
We call \( \pi_{k,i} \) the \emph{projection} functions, \( c_{k,\varepsilon} \) the \emph{constant} functions, and \( s \) the \emph{successor} function.

Let \( f \colon \mathbb W^m \rightharpoonup \mathbb W \) and \( g_1, \dots, g_m \colon \mathbb W^k \rightharpoonup \mathbb W \).
Then their \emph{composition} is the function \( h(\vb w) = f(g_1(\vb w), \dots, g_m(\vb w)) \).

Let \( f \colon \mathbb W^k \rightharpoonup \mathbb W \) and \( g \colon \mathbb W^{k+2} \rightharpoonup \mathbb W \).
Then the partial function \( h \colon \mathbb W^{k+1} \rightharpoonup \mathbb W \) defined by \( h(\vb w, \varepsilon) = f(\vb w) \) and \( h(\vb w, s(v)) = g(\vb w, v, h(\vb w, v)) \) is a function defined by \emph{recursion}.

Let \( f \colon \mathbb W^{k+1} \rightharpoonup \mathbb W \).
Then the function \( h \colon \mathbb W^k \rightharpoonup \mathbb W \) defined by
\[ h(\vb w) = \begin{cases}
	v & \text{if for all \( u \leq v \), we have \( f(\vb w, u) \downarrow \) and \( v \) is \( < \)-minimal such that \( f(\vb w, v) = \varepsilon \)} \\
	\uparrow & \text{if there is no \( v \) satisfying the above property}
\end{cases} \]
is a function defined by \emph{minimisation}.
\begin{remark}
	If a class of functions has the basic functions and is closed under composition, it has all constant functions \( c_{k,v}(\vb w) = v \), because if \( v = s^k(\varepsilon) \), \( c_{k,v} = s^k \circ c_{k,\varepsilon} \).
\end{remark}
\begin{definition}
	A class \( \mathcal C \) of partial functions is closed under composition, recursion, and minimisation if whenever \( f_1, \dots, f_\ell \in \mathcal C \), then the results of applying these operations also lie in \( \mathcal C \).
\end{definition}
\begin{remark}
	The class \( \mathcal P \) of all partial functions is closed under composition, recursion, and minimisation.
\end{remark}
\begin{definition}
	We call a partial function \emph{recursive} if it lies in the smallest class \( \mathcal C \) that contains the basic functions and is closed under composition, recursion, and minimisation.
	A partial function is \emph{primitive recursive} if it lies in the smallest class \( \mathcal C \) that contains the basic functions and is closed under composition and recursion.
\end{definition}
\begin{example}
	\( \pi_{1,0} \colon \mathbb W^1 \to \mathbb W \) is the identity function, which is primitive recursive.
	\( \pi_{3,2} \colon \mathbb W^3 \to \mathbb W \) defined by \( \pi_{3,2}(u,v,w) = w \) is primitive recursive as it is a basic function.
	The successor function \( s \colon \mathbb W \to \mathbb W \) is primitive recursive.
	The function \( s \circ \pi_{3,2} \) is primitive recursive, as the composition of primitive recursive functions.

	The function \( h \) defined by \( h(w,\varepsilon) = \pi_{1,0}(w) \) and \( h(w,s(v)) = s \circ \pi_{3,2}(w,v,h(w,v)) = s(h(w,v)) \) is primitive recursive, which is exactly the addition function \( \# h(n,m) = \# n + \# m \).
	We can define multiplication and exponentiation in a similar way, and so all of these are primitive recursive.
\end{example}
We can encode recursive functions in trees.
Let \( T \) be a finitely branching tree, and define a labelling \( \ell \) on \( T \) with the labels
\begin{center}
	\begin{tabular}{c c c c}
		& label & arity & branching number \\
		projection & \( B_{k,i}^\pi \) & \( k \) & 0 \\
		constant & \( B_{k,i}^c \) & \( k \) & 0 \\
		successor & \( B^s \) & 1 & 0 \\
		composition & \( C_{n,k} \) & \( k \) & \( n + 1 \) \\
		recursion & \( R_k \) & \( k + 1 \) & 2 \\
		minimisation & \( M_k \) & \( k \) & 1
	\end{tabular}
\end{center}
\begin{definition}
	A tree \( T \) with a labelling \( \ell \) is called a \emph{recursion tree} if the branching of the tree corresponds exactly to the branching numbers of its labels, and
	\begin{enumerate}
		\item if \( \ell(s) = C_{n,k} \), then the first successor of \( s \) has a label of arity \( n \) and all other have labels with arity \( k \);
		\item if \( \ell(s) = R_k \), then the first successor of \( s \) has arity \( k \) and the other has arity \( k + 2 \);
		\item if \( \ell(s) = M_k \), then the successor has arity \( k \).
	\end{enumerate}
	A recursion tree is \emph{primitive} if it has no minimisation labels \( M_k \).
\end{definition}
The following recursion tree describes the addition function defined above.
\begin{center}
	\begin{tikzcd}
		& {R_1} \\
		{B_{1,0}^\pi} && {C_{1,3}} \\
		& {B^s} && {B_{3,2}^\pi}
		\arrow[no head, from=1-2, to=2-1]
		\arrow[no head, from=1-2, to=2-3]
		\arrow[no head, from=2-3, to=3-4]
		\arrow[no head, from=2-3, to=3-2]
	\end{tikzcd}
\end{center}
We can assign a (partial) recursive function \( f_{T,\ell} \) to every recursive tree \( (T, \ell) \).
If the tree is primitive, the function obtained is primitive recursive.
\begin{theorem}
	A partial function \( f \) is recursive if and only if there is a recursion tree \( (T, \ell) \) such that \( f = f_{T, \ell} \).
	It is primitive recursive if it admits a recursion tree that is primitive.
\end{theorem}
\begin{proof}
	We can obtain the associated partial function from a recursion tree by induction on the height on the tree.
	For the converse, it suffices to show that the class of functions \( f_{T,\ell} \) contains the basic functions and is closed under composition, recursion, and minimisation, which holds by construction.
\end{proof}
\begin{theorem}
	Every partial recursive function is computable.
\end{theorem}
\begin{proof}
	The basic functions have already been shown to be computable.
	Computable functions are closed under composition (previously called concatenation).
	So it suffices to show that the computable functions are closed under recursion and minimisation.

	Let \( f, g \) be computable functions; we want to show that \( h \) defined by \( h(\vb w, \varepsilon) = f(\vb w) \) and \( h(\vb w, s(v)) = g(\vb w, v, h(\vb w, v)) \) is computable.
	We describe a register machine.
	% TODO: Fix this, as (iii)(a) has v bound and (iii)(b) has v free
	\begin{enumerate}
		\item Let \( k, \ell \) be two empty unused registers.
		\item Compute \( f(\vb w) \), and write the result to register \( \ell \).
			Note that if \( f(\vb w) \) is undefined, this produces the desired result.
		\item If \( v = \varepsilon \), output the content of register \( \ell \).
			Otherwise, apply the successor function \( s \) to register \( k \) and perform the following subroutine.
			\begin{enumerate}
				\item Compute \( g(\vb w, v, u) \) where \( u \) is the content of register \( \ell \), then overwrite register \( \ell \) with the result.
				\item Check whether \( v \) is equal to the register content of \( k \).
					If so, output register \( \ell \).
					Otherwise, apply \( s \) to register \( k \) and restart the subroutine.
			\end{enumerate}
	\end{enumerate}
	We now consider minimisation.
	Let \( f \) be computable.
	Let \( k \) be empty and unused.
	Perform the following subroutine.
	\begin{enumerate}
		\item Compute \( f(\vb w, u) \) where \( u \) is the content of register \( k \).
			If this result is undefined, this is the desired result.
		\item Check whether the computation result is empty.
			If it is empty, output the register content of \( k \).
			Otherwise, apply the successor function \( s \) to \( k \) then restart the subroutine.
	\end{enumerate}
\end{proof}
\begin{remark}
	The proof showed that the computable functions are closed under recursion and minimisation, not just that all partial recursive functions are computable.
	Therefore, we can use recursion and minimisation directly to construct computable functions or register machines.
\end{remark}

\subsection{Merging and splitting words}
There is a bijection \( z \colon \mathbb N \times \mathbb N \to \mathbb N \), called the \emph{Cantor zigzag function}.
\[ z(i,j) = \frac{(i+j)(i+j+1)}{2} + j \]
This gives a bijection \( \mathbb W \times \mathbb W \to \mathbb W \).
All of these operations are computable by register machines.
\begin{definition}
	Let \( v, w \) be words.
	Then we can \emph{merge} the two words into \( v \ast w \), which is the unique word such that \( \#(v \ast w) = z(\#v, \#w) \).
	We can \emph{split} a word \( w \) into \( u, v \) such that \( \#w = z(\#u, \#v) \).
	We write \( u = w_{(0)} \) and \( v = w_{(1)} \).
\end{definition}
Technically, splitting a word is not a computable function, since computable functions are defined to always have codomain \( \mathbb W \).
However, the operation of splitting a word can be performed.

\subsection{Universality}
Consider an alphabet \( \Sigma \).
We then have a notion of computability for sets \( X \subseteq \Sigma^\star = \mathbb W \).
If \( \Sigma \subseteq \Sigma' \), then every \( \Sigma \)-register machine is a \( \Sigma' \)-register machine.
However, the notion of \( \Sigma' \)-computability is no stronger than \( \Sigma \)-computability.
One can show that computability over any alphabet \( \Sigma \) with \( \abs{\Sigma} \geq 2 \) is equivalent to computability over the set \( \qty{0,1} \) by encoding each letter as a binary string.

In this subsection, we aim to show that there is a \emph{universal} register machine, which is a machine that can mimic every register machine.
Let \( \Sigma \) be an alphabet, and add additional symbols
\[ \bm 0\ \bm 1\ \bm +\ \bm -\ \bm ?\ \bm (\ \bm )\ \bm ,\ \bm \mapsto\ \bm \mdwhtsquare \]
We name the new alphabet \( \Sigma' \).
When we encode a mathematical object \( o \) as a word \( \Sigma'^\star \), we write the encoded result \( \code(o) \).
\begin{itemize}
	\item We can encode \( \mathbb N \) in binary using \( \bm 0 \) and \( \bm 1 \), for instance, \( \code(19) = \bm 1 \bm 0 \bm 0 \bm 1 \bm 1 \).
	\item If \( Q = \qty{q_0, \dots, q_k} \), we define \( \code(q_k) = \code(k) \).
	\item We encode instructions \( I \in \mathrm{Instr}(\Sigma, Q) \) using \( \bm +\ \bm -\ \bm ?\ \bm ,\ \bm (\ \bm ) \); for instance, \( \code(+(k,a,\ell)) = \bm +\bm(\code(k)\bm , a\bm ,\code(\ell)\bm ) \).
	\item We encode program lines by \( \code(q \mapsto I) = \code(q) \bm \mapsto \code(I) \).
	\item We encode a register machine with program \( P \) as \( \code(q_0 \mapsto P(q_0)) \bm , \ldots \bm , \code(q_n \mapsto P(q_n)) \).
	\item We encode sequences of words by \( \vb w \) by \( \code(\vb w) = \bm\mdwhtsquare w_0 \bm\mdwhtsquare \ldots \bm\mdwhtsquare w_k \bm\mdwhtsquare \).
	\item We encode configurations \( (q, \vb w) \) by \( \code(q)\code(\vb w) \).
\end{itemize}
\begin{lemma}
	The function \( h \) defined by
	\[ h(w,u,v) = \begin{cases}
		\code(C(M,\vb w,\# v)) & \text{if } \exists M, \vb w \text{ such that } w = \code(M), u = \code(\vb w) \\
		\uparrow & \text{otherwise}
	\end{cases} \]
	is computable.
\end{lemma}
\begin{proof}
	Define by recursion
	\[ h(\code(M), \code(\vb w), \varepsilon) = \code(q_0)\code(\vb w);\quad h(\code(M), \code(\vb w), s(v)) = \code(C') \]
	where \( C' \) is the result of transforming \( h(\code(M), \code(\vb w), v) \) by the machine \( M \).
\end{proof}
\begin{corollary}
	The \emph{truncated computation} function \( t_{M,k} \) defined by
	\[ t_{M,k}(\vb w, v) = \begin{cases}
		a & M \text{ has halted before time } \#v \text{ on input } \vb w \\
		\varepsilon & \text{otherwise}
	\end{cases} \]
	is computable.
\end{corollary}
\begin{proof}
	Using recursion on the function \( h \) from the previous lemma, we check all values of \( h \) for words \( u \) such that \( \# u < \# v \).
	If any of the values is in state \( q_H \), output \( a \), otherwise, output \( \varepsilon \).
\end{proof}
\begin{theorem}[the software principle]
	The function \( g \) defined by
	\[ g(v,u) = \begin{cases}
		f_{M,k}(\vb w) & \text{if } v = \code(M), u = \code(\vb w) \text{ and \( \vb w \) has length \( k \)} \\
		\uparrow & \text{otherwise}
	\end{cases} \]
	is computable.
\end{theorem}
\begin{proof}
	We have a computable function \( f \) that maps \( w, u, v \) to \( \code(C(M,\vb w, \# v)) \) if \( \code(M) = w \) and \( \code(\vb w) = u \) by the previous lemma.
	We start by checking whether \( w \) is a code for a register machine and \( u \) is a code for a \( k \)-tuple of words; if not, never halt.
	Write \( f' \) for the computable function mapping \( w, u, v \) to \( a \) if the state of \( f(w,u,v) \) is \( q_H \), and \( \varepsilon \) otherwise.
	We minimise \( f' \) to obtain the computable function \( h \), such that \( h(w,u) \) is the least \( v \) such that \( f(w,u,v) \) is in state \( q_H \) if it exists.
	If \( h(w,u) \) does not halt, then there is no step at which the computation halts, as expected, since \( g(w,u) \) should not halt in this case.
	If \( h(w,u) \) halts, consider the configuration \( C(M,\vb w, \#h(w,u)) \) and find the code for its 0th register, and write this into the actual 0th register.
\end{proof}
\begin{remark}
	A register machine \( U \) that computes \( g \) is called a \emph{universal register machine}.
	\( U \) has a finite amount of used registers and states, but can mimic the behaviour of any register machine using an arbitrarily large amount of registers and states.

	This allows us to streamline notation; for a word \( v \in \mathbb W \), we can write
	\[ f_{v,k}(\vb w) = f_{U,2}(v,\code(\vb w)) = f_{M,k}(\vb w) \]
	if \( \code(M) = v \).
	Similarly, we can write \( W_v = \dom f_{v,1} \), so \( \qty{W_v \mid v \in \mathbb W} \) is the set of computably enumerable sets.
\end{remark}
\begin{theorem}[\( s \)--\( m \)--\( n \) theorem; parameter theorem]
	Let \( g \colon \mathbb W^{k+1} \rightharpoonup \mathbb W \) be computable.
	Then there exists a total computable function \( h \colon \mathbb W \to \mathbb W \) such that \( f_{h(v),k}(\vb w) = g(\vb w, v) \).
\end{theorem}
This process is called \emph{currying}, after Haskell Curry.
\begin{remark}
	\( g_v(\vb w) = g(\vb w, v) \) is a function in \( k \) variables.
	This is computable, so there is a mathematical function \( h \) such that \( g_v = f_{h(x),k} \), but this \( h \) is not \emph{a priori} computable.
\end{remark}
\begin{proof}
	First, the operation \( \vb w \mapsto (\vb w, v) \) is performed by a register machine \( M_v \); this is the register machine that writes \( v \) into register \( k \).
	Therefore, we have a computable function \( v \mapsto \code(M_v) \).
	Now, since \( g \) is computable, there is a register machine \( M \) such that \( f_{M,k+1} = g \).
	Therefore, \( g_v \) is computed by the sequence of register machines \( M_v \) then \( M \).
	We can computably concatenate two register machines, so we can compute a code for \( M \circ M_v \).
	Hence the function \( h(v) = \code(M \circ M_v) \) is total and computable.

	We must show that \( f_{h(v),k}(\vb w) = g(\vb w, v) \).
	Indeed,
	\[ f_{h(v),k}(\vb w) = f_{\code(M \circ M_v), k}(\vb w) = f_{M \circ M_v, k}(\vb w) = g_v(\vb w) = g(\vb w, v) \]
	as required.
\end{proof}

\subsection{The halting problem}
Consider the sets
\[ \mathbb K_0 = \qty{(w, v) \mid f_{w,1}(v) \downarrow};\quad \mathbb K = \qty{w \mid f_{w,1}(w) \downarrow} \]
\begin{theorem}
	\( \mathbb K_0 \) and \( \mathbb K \) are computably enumerable.
\end{theorem}
\begin{proof}
	It suffices to show that \( \mathbb K_0, \mathbb K \) are the domains of computable functions.
	By the software principle, \( f_{U,2}(w,v) = f_{w,1}(v) \) and \( \dom f_{U,2} = \mathbb K_0 \) as required.
	Observe that the diagonal function \( \Delta(w) = (w, w) \) is computable, so \( f_{U,2} \circ \Delta \) is computable, and \( \dom(f_{U,2} \circ \Delta) = \mathbb K \).
\end{proof}
\begin{theorem}[the halting problem]
	Neither \( \mathbb K_0 \) nor \( \mathbb K \) are computable.
\end{theorem}
\begin{proof}
	We prove the result for \( \mathbb K_0 \).
	Suppose that \( \mathbb K_0 \) is computable, so the characteristic function \( \chi_{\mathbb K_0} \) is computable.
	Now, define
	\[ f(w) = \begin{cases}
		\uparrow & \text{if } \chi_{\mathbb K_0}(w,w) = a \\
		\varepsilon & \text{if } \chi_{\mathbb K_0}(w,w) = \varepsilon
	\end{cases} \]
	This is a computable function, so there is a machine \( d \in \mathbb W \) such that \( f_{d,1} = f \).
	Now,
	\[ f(d) \downarrow \iff f_{d,1}(d) \downarrow \iff (d,d) \in \mathbb K_0 \iff \chi_{\mathbb K_0}(d,d) = a \iff f(d) \uparrow \]
	The proof is almost exactly the same for \( \mathbb K \).
\end{proof}

\subsection{Sets with quantifiers}
\begin{definition}
	\( X \subseteq \mathbb W^k \) is called \( \Sigma_1 \) if there is a computable set \( Y \subseteq \mathbb W^{k+1} \) such that \( \vb w \in X \iff \exists y, (\vb w, y) \in Y \).
	We say \( X = p(Y) = \qty{\vb w \mid \exists y,\, (\vb w, y) \in Y} \) is the \emph{projection} of \( Y \).
	We say \( X \) is \( \Pi_1 \) if it is the complement of a \( \Sigma_1 \) set.
	We say \( X \) is \( \Delta_1 \) if it is \( \Sigma_1 \) and it is \( \Pi_1 \).
\end{definition}
\begin{remark}
	The notation \( \Sigma \) is chosen to symbolise an existential quantifier, and \( \Pi \) symbolises the universal quantifier.
	In logic, sums and existentials are related, and products and universal quantifiers are also related.
	\( \Delta \) is chosen for the German word \emph{Durchschnitt} (`intersection'), as \( \Delta_1 \) is the intersection of \( \Sigma_1 \) and \( \Pi_1 \).
\end{remark}
\begin{proposition}
	Every computable set is \( \Delta_1 \).
\end{proposition}
\begin{proof}
	By closure under complement, it suffices to show every computable set is \( \Sigma_1 \).
	The computable set \( Y = \qty{(\vb w, y) \mid \vb w \in X} \) has projection \( X \).
	Logically, this adds a trivial existential quantification.
\end{proof}
\begin{theorem}
	The computably enumerable sets are exactly the \( \Sigma_1 \) sets.
\end{theorem}
\begin{proof}
	Suppose \( X \) is computably enumerable.
	Then by definition, the pseudocharacteristic function \( \psi_X \) is computable.
	Then there exists a register machine \( M \) such that \( \psi_X = f_{M,k} \).
	We define \( Y = \qty{(\vb w, y) \mid t_{M,k}(\vb w, y) = a} \) where \( t_{M,k} \) is the truncated computation function for the register machine \( M \).
	\( Y \) is computable, since \( t_{M,k} = \chi_Y \).
	Then \( \vb w \in X \iff \psi_X(\vb w) \downarrow \iff \exists y,\, (\vb w, y) \in Y \) as required.

	Now suppose \( X \) is \( \Sigma_1 \).
	Let \( Y \) be a computable set such that \( X = p(Y) \).
	As the computable sets are closed under complement, the characteristic function \( \chi_{Y^c} \) is computable.
	We apply minimisation to \( \chi_{Y^c} \) to obtain a function \( h \) such that \( h(\vb w) \) is the minimal \( y \) such that \( (\vb w, y) \in Y \).
	Then \( \dom h = p(Y) = X \), so \( X \) is the domain of a partial computable function as required.
\end{proof}
\begin{example}
	Let \( f \colon \mathbb W^2 \rightharpoonup \mathbb W \) be a partial computable function in two variables.
	Then \( X = \qty{w \mid \exists v,\, f(w, v) \downarrow} \) is computably enumerable.
	Note that \( f(w, v) \downarrow \) is not a computable predicate.
	Let \( M \) be a register machine such that \( f = f_{M,2} \), and let
	\[ Z = \qty{(w, v_0, v_1) \mid t_{M,2}(w,v_0,v_1) = a} \]
	Clearly \( Z \) is computable.
	Define
	\[ Y = \qty{(w, u) \mid (w, u_{(0)}, u_{(1)}) \in Z} \]
	This is also computable.
	Now,
	\begin{align*}
		\exists v,\, f(w,v) \downarrow &\iff \exists v_0,\, \exists v_1,\, (w,v_0,v_1) \in Z \\
		&\iff \exists u,\, (w,u_{(0)},u_{(1)}) \in Z \\
		&\iff (w,u) \in Y \\
		&\iff w \in p(Y)
	\end{align*}
	So \( X \) is \( \Sigma_1 \) as required.
\end{example}
\begin{remark}
	The previous argument is sometimes known as a \emph{zigzag argument}; a pair of existential quantifiers can be merged into a single existential by merging the two words.
	Hence, we can perform infinitely many computations in parallel.
\end{remark}
\begin{corollary}
	The computable sets are exactly the \( \Delta_1 \) sets.
\end{corollary}
\begin{proof}
	If \( X \) is computable, it must be \( \Delta_1 \) by a previous result.
	If \( X \) is \( \Delta_1 \), we can use a zigzag technique.
	We know that there are machines \( M, M' \) such that \( w \in X \iff \exists v,\, t_{M,k}(\vb w, v) = a \) and \( w \not\in X \iff \exists v,\, t_{M',k}(\vb w, v) = a \).
	Now, consider
	\[ f(\vb w, v) = \begin{cases}
		t_{M,k}(\vb w, v_{(1)}) & \#v_{(0)} \text{ is even} \\
		t_{M',k}(\vb w, v_{(1)}) & \#v_{(0)} \text{ is odd}
	\end{cases} \]
	This is computable.
	Apply minimisation to \( f \) to obtain a function \( h \) where \( h(\vb w) \) is the least \( v \) such that \( f(\vb w, v) \neq \varepsilon \).
	We output \( a \) if \( \#h(\vb w)_{(0)} \) is even, and \( \varepsilon \) if \( \#h(\vb w)_{(0)} \) is odd.
\end{proof}
\begin{corollary}
	\( \Sigma_1 \) is not closed under complement.
\end{corollary}
\begin{proof}
	The complement of the halting set \( \mathbb W \setminus \mathbb K \) is \( \Pi_1 \) and not \( \Delta_1 \), so not \( \Sigma_1 \).
\end{proof}
\begin{theorem}
	Every type 0 language is computably enumerable.
\end{theorem}
\begin{proof}
	Let \( G = (\Sigma, V, P, S) \) and let \( \Sigma' = \Omega \cup \qty{\bm\to} \).
	We encode derivations as \( \sigma_0 \bm\to \cdots \bm\to \sigma_n \); this is a \( \Sigma' \)-word.
	We say \( w \in (\Sigma')^\star \) is a \emph{derivation code} if \( w \) is of this form with \( (\sigma_0, \dots, \sigma_n) \) a \( G \)-derivation.
	In this case, we call \( \sigma_0 \) the \emph{initial string} and \( \sigma_n \) the \emph{final string}.
	Let
	\[ Y = \qty{(w, v) \mid v \text{ is a derivation code with initial string } S \text{ and final string } w} \]
	\( Y \) is computable since we can produce a register machine that tests if a given derivation code can be produced from a fixed given grammar.
	But \( w \in \mathcal L(G) \iff \exists v,\, (w, v) \in Y \).
	This is \( \Sigma_1 \), as required.
\end{proof}
\begin{remark}
	The converse also holds; every computably enumerable set \( X \subseteq \mathbb W \) is a type 0 language.
	This will not be proven rigorously in this course; a sketch will be provided later.
\end{remark}

\subsection{Closure properties}
\begin{proposition}
	The computable sets are closed under intersection, union, complement, difference, and concatenation.
\end{proposition}
\begin{proof}
	Let \( A, B \) be computable sets, so \( \chi_A, \chi_B \) are computable functions.
	We obtain
	\[ \chi_{A \cap B}(\vb w) = \begin{cases}
		a & \chi_A(\vb w) = a \text{ and } \chi_B(\vb w) = a \\
		\varepsilon & \text{otherwise}
	\end{cases} \]
	For complement,
	\[ \chi_{\mathbb W \setminus A}(\vb w) = \begin{cases}
		a & \chi_A(\vb w) = \varepsilon \\
		\varepsilon & \text{otherwise}
	\end{cases} \]
	For concatenation, we suppose \( A, B \subseteq \mathbb W \) are one-dimensional.
	Given a word \( w \), we can iterate over all possible decompositions \( w = vu \) and check if \( v \in A, u \in B \).
	There are \( (\abs{w} + 1) \)-many such decompositions, so this minimisation will always halt.
\end{proof}
\begin{remark}
	The result for intersection is analogous to the product construction from deterministic automata; two computable functions can be evaluated in parallel since they always terminate, and then their results may be combined.
\end{remark}
\begin{proposition}
	The computably enumerable sets are closed under intersection, union, and concatenation.
	They are not closed under complement or difference.
\end{proposition}
\begin{proof}
	We have already shown that the complement of the halting set \( \mathbb K \) is \( \Pi_1 \) but not \( \Sigma_1 \), so the computably enumerable sets are not closed under complement or difference.
	For intersection, the same construction as before works.
	\[ \chi_{A \cap B}(\vb w) = \begin{cases}
		a & \psi_A(\vb w) = a \text{ and } \psi_B(\vb w) = a \\
		\uparrow & \text{otherwise}
	\end{cases} \]
	This is because if \( \psi_A \) or \( \psi_B \) diverge, the result is \( \uparrow \) as desired.
	For union, we cannot compute \( \psi_A \) and \( \psi_B \) serially, since if \( \psi_A \uparrow \) we never run \( \psi_B \) at all.
	Using the zigzag technique, we can check \( \psi_A(\vb w) \) and \( \psi_B(\vb w) \) in parallel, halting if either halts at any time index.
	This idea is elaborated on an example sheet.

	For concatenation, consider the set \( Z \) of triples \( (w, v, u) \) such that \( v \) is an initial segment of \( w \), and after \( \#u \) steps, \( \psi_A(v) = a \) and \( \psi_B(v') = a \), where \( w = vv' \).
	Now define \( Y = \qty{(w, u) \midd (w, u_{(0)}, u_{(1)}) \in Z} \), so \( w \in AB \) if and only if there exists \( v \) such that \( (w, v) \in Y \).
\end{proof}
\begin{proposition}
	\( X \) is computably enumerable if and only if there is a partial computable function \( f \) such that \( X = \Im f \).
\end{proposition}
\begin{remark}
	In fact, a stronger result is true: \( X \) is computably enumerable if and only if there is a \emph{total} computable function \( f \) such that \( X = \Im f \).
	This is seen on an example sheet.
	This result justifies the name `computably enumerable'.
\end{remark}
\begin{proof}
	If \( \psi_X \) is computable, then so is
	\[ f(w) = \begin{cases}
		w & \psi_X(w) \downarrow \\
		\uparrow & \text{otherwise}
	\end{cases} \]
	Clearly \( \Im f = X \) as required.

	Conversely, suppose \( f \colon \mathbb W \rightharpoonup \mathbb W \) with \( X = \Im f \).
	Suppose \( f = f_{c,1} \).
	We use the zigzag technique.
	Define the set \( Z \) of tuples \( (w, v, u) \) such that \( t_{c,1}(v,u) = a \) and \( f_{c,1}(v) = w \).
	Let \( Y = \qty{(w,v) \midd (w, v_{(0)}, v_{(1)}) \in Z} \), so \( \Im f = p(Y) \).
\end{proof}

\subsection{The Church--Turing thesis}
Register machines and recursive functions can both be used to define computability.
Historically, \emph{Turing machines} were also used to define and analyse computability.
There is another alternative, known as \emph{while programs}.
Notably, in this model, there is no special `halt state'; the program halts simply when there are no more instructions to execute.
Therefore the computation sequence in this model may be finite.
This gives rise to a notion of while computable functions, the functions computed by a while program.

\begin{theorem}
	Let \( f \colon \mathbb W^k \rightharpoonup \mathbb W \).
	Then, the following are equivalent.
	\begin{enumerate}
		\item \( f \) is (register machine) computable.
		\item \( f \) is partial recursive.
		\item \( f \) is Turing computable.
		\item \( f \) is while computable.
	\end{enumerate}
\end{theorem}
Turing machines, register machines, recursive functions, and while programs are superficially completely different approaches, yet the classes of computable functions that they define are exactly identical.
The \emph{Church--Turing thesis} is that this is universal; any reasonable notion of computation is equivalent.
Unfortunately, this is a nonmathematical statement, and cannot be made precise; this is simply a statement that describes our intuition about what computation means.
Accepting this thesis allows us to freely choose which notion of computability we would like to use for a given task.

The following is a proof sketch of the fact that computably enumerable sets are type 0 languages.
The sketch makes use of the fact that Turing computability is exactly register machine computability.
For more detail, see \emph{Formal Languages} (Salomaa 1973).
\begin{proof}[Proof sketch]
	Let \( M \) be a Turing machine computing \( \psi_X \).
	Without loss of generality, let the read-write head be then moved to the front, so \( q_s \mdwhtsquare w \mdwhtsquare \xrightarrow M q_H \mdwhtsquare a \mdwhtsquare \).
	This is a rewrite system with the rules described by the definition of the Turing machine, transforming \( q_S \mdwhtsquare w \mdwhtsquare \) into \( q_H \mdwhtsquare a \mdwhtsquare \)

	We define a grammar which starts from \( S \), with \( S \to q_H \mdwhtsquare a \mdwhtsquare \), and performs all Turing instructions backwards.
	When \( q_S \) is seen, it deletes everything except \( w \).
\end{proof}

\subsection{Solvability of decision problems}
We can use the Church--Turing thesis to give precise statements of our decision problems, without relying on an informal notion of `algorithm'.
First, we encode grammars in such a way that for all \( w \in \mathbb W \), there exists a grammar \( G \) such that \( \code(G) = w \); we write \( G_w \) for the associated grammar for a word.
We require that all grammars are of the form \( G_w \) for some word \( w \in \mathbb W \).
Now,
\begin{enumerate}
	\item the word problem is \( \qty{(w, v) \mid w \in \mathcal L(G_v)} \);
	\item the emptiness problem is \( \qty{w \mid \mathcal L(G_w) = \varnothing} \);
	\item the equivalence problem is \( \qty{(w, v) \mid \mathcal L(G_w) = \mathcal L(G_v)} \).
\end{enumerate}
These are sets of tuples of words, so we can use our notion of computability.
We can now concretely define that such a problem is \emph{solvable} if the set is computable.
\begin{theorem}
	The word problem for type 0 grammars is unsolvable.
\end{theorem}
\begin{proof}
	Let \( W = \qty{(w, v) \mid w \in \mathcal L(G_v)} \).
	We want to show that \( W \) is not computable.
	Recall that \( \mathbb K_0 = \qty{(w, v) \mid f_{w,1}(v) \downarrow} \); we will use a proof analogous to the one used for this set.
	Suppose \( W \) is computable, so let
	\[ f(w) = \begin{cases}
		\uparrow & w \in \mathcal L(G_w) \\
		a & w \not\in \mathcal L(G_w)
	\end{cases} \]
	Then \( f \) is a computable function.
	Hence, \( \dom f \) is computably enumerable.
	So there exists a grammar \( G \) such that \( \mathcal L(G) = \dom f \).
	Let \( d \in \mathbb W \) be such that \( G = G_d \).
	Then
	\[ d \in \mathcal L(G_d) \iff d \in \dom f \iff d \not\in \mathcal L(G_d) \]
\end{proof}

\subsection{Reduction functions}
\begin{definition}
	Let \( A, B \subseteq \mathbb W \).
	A function \( f \colon \mathbb W \to \mathbb W \) is called a \emph{reduction} from \( A \) to \( B \) if \( f \) is total computable and \( w \in A \) if and only if \( f(w) \in B \).
	We write \( A \leq_m B \) if there is a reduction from \( A \) to \( B \).
\end{definition}
\begin{remark}
	Given a reduction \( f \) from \( A \) to \( B \), the set \( A \) is intuitively `at most as complicated as \( B \)'.
	Note that \( f^{-1}(B) = A \).
\end{remark}
The subscript \( m \) in the notation \( A \leq_m B \) stands for `many-one'; the function \( f \) need not be injective.
Note that \( \leq_m \) is reflexive and transitive.
This relation respects complements: \( A \leq_m B \) implies \( \mathbb W \setminus A \leq_m \mathbb W \setminus B \).
The relation is not in general antisymmetric, so this does not form a partial order.
Instead, \( \leq_m \) forms a (partial) preorder.

If \( \leq \) is a preorder on a set \( X \), we can define the equivalence relation \( x \sim y \) when \( x \leq y \) and \( y \leq x \).
Then \( \qty(\faktor{X}{\sim}, \leq) \) is a partial order.
A preorder can therefore be understood as a partial order, except that instead of ordering single elements, it orders clusters of equivalent elements.

If \( A \leq_m B \) and \( B \) is computable, then \( A \) is also computable.
Similarly, if \( A \leq_m B \) and \( B \) is computably enumerable, then \( A \) is also computably enumerable.
This demonstrates the fact that \( \chi_A = \chi_B \circ f \) and \( \psi_A = \psi_B \circ f \), where \( f \) is the reduction.

Note that if \( A \leq_m B \) and \( A \) is not computable, then \( B \) is also not computable, and a similar result holds for sets that are not computably enumerable.
In particular, if \( \mathbb K \leq_m A \), then \( A \) is not computable.
If \( \mathbb W \setminus \mathbb K \leq_m A \), then \( A \) is not computably enumerable.
\begin{remark}
	Many of the previous proofs in this section have implicitly used the notion of a reduction function, for instance, the claim that solvability of the set \( \qty{(w, v) \mid w \in \mathcal L(G_v)} \) is equivalent to solvability of the set \( \qty{(w, v) \mid w \in W_v} \).
\end{remark}
\begin{proposition}
	Let \( A \) be a computable set, and \( B \neq \varnothing, \mathbb W \).
	Then \( A \leq_m B \).
\end{proposition}
\begin{proof}
	Since \( B \neq \varnothing, \mathbb W \), let \( v \in B, u \not\in B \).
	Since \( A \) is computable, we have the computable function
	\[ f(w) = \begin{cases}
		v & w \in A \\
		u & w \not\in A
	\end{cases} \]
	This is a reduction from \( A \) to \( B \) as required.
\end{proof}
Note that \( \mathbb W \setminus \mathbb K \not\leq_m \mathbb K \), otherwise \( \mathbb K \) is not computably enumerable.
We also have \( \mathbb K \not\leq_m \mathbb W \setminus \mathbb K \) from the first result, after considering complements.
There are therefore various different \emph{degrees of unsolvability}: equivalence classes of \( \leq_m \) that are strictly larger than the class of computable sets.

There are many more such classes than the ones containing \( \mathbb K \) and \( \mathbb W \setminus \mathbb K \).
Let \( \qty{0, 1} \subseteq \Sigma \).
If \( A, B \) are sets, we can define the \emph{Turing join} \( A \oplus B = 0A \cup 1B \).
Then \( A \leq_m A \oplus B \) and \( B \leq_m A \oplus B \).
The Turing join produces an upper bound in the set of equivalence classes of sets of words, and it can be shown that this is the least upper bound.
Hence we obtain another class of sets represented by \( \mathbb K \oplus \mathbb W \setminus \mathbb K \).
This is neither \( \Sigma_1 \) nor \( \Pi_1 \).

\begin{definition}
	If \( \mathcal C \) is a class of sets, we say that \( A \) is \emph{\( \mathcal C \)-hard} if for all \( B \in \mathcal C \), we have \( B \leq_m A \).
	We say that \( A \) is \emph{\( \mathcal C \)-complete} if it is \( \mathcal C \)-hard and \( A \in \mathcal C \).
\end{definition}
\begin{remark}
	A \( \mathcal C \)-hard set is `at least as hard as \( \mathcal C \)'.
	A \( \mathcal C \)-complete set is the `most complicated' \( \mathcal C \) set.
\end{remark}
\begin{corollary}
	Let \( A \) be \( \Delta_1 \) and \( A \neq \varnothing, \mathbb W \).
	Then \( A \) is \( \Delta_1 \)-complete.
\end{corollary}
\begin{proof}
	The \( \Delta_1 \) sets are the computable sets, so we simply apply the previous proposition.
\end{proof}
\begin{theorem}
	\( \mathbb K \) is \( \Sigma_1 \)-complete.
\end{theorem}
\begin{proof}
	Clearly \( \mathbb K \in \Sigma_1 \).
	Now, let \( X \) be an arbitrary set in \( \Sigma_1 \), so \( X \) is computably enumerable.
	Let \( f \) be a partial computable function such that \( X = \dom f \).
	It suffices to show \( X \leq_m \mathbb K \).

	Consider the function \( g(w,u) = f(w) \).
	This is computable.
	We can therefore apply the \( s \)--\( m \)--\( n \) theorem to obtain a total computable function \( h \) such that \( f_{h(w)}(u) = g(w,u) = f(w) \).
	We claim that \( h \) is a reduction function from \( X \) to \( \mathbb K \).

	Suppose \( w \in X \).
	Then \( w \in \dom f \), so \( f_{h(w)} \) is the constant function \( f(w) \).
	Hence \( W_{h(w)} = \mathbb W \).
	So \( f \) is total, and therefore \( f_{h(w)}(h(w)) \downarrow \).
	So \( h(w) \in \mathbb K \).

	Now suppose \( w \not\in X \), so \( w \not\in \dom f \).
	Then \( f_{h(w)} \) does not halt for any input, giving \( W_{h(w)} = \varnothing \).
	So \( f_{h(w)}(h(w)) \uparrow \) and in particular \( h(w) \not\in \mathbb K \).
\end{proof}

\subsection{Rice's theorem}
We say that \( M \) and \( M' \) are weakly equivalent when \( \dom f_{M,1} = W_M = W_{M'} = \dom f_{M',1} \).
We can extend this to words.
Words \( v, u \) are weakly equivalent when \( W_v = W_u \), and write \( v \sim u \).
\begin{definition}
	A set \( I \subseteq \mathbb W \) is called an \emph{index set} if it is closed under weak equivalence.
\end{definition}
\begin{remark}
	Index sets are unions of equivalence classes.
\end{remark}
\begin{example}
	\( \varnothing \) and \( \mathbb W \) are the trivial index sets.
	Other index sets correspond to properties of computably enumerable sets.
	\( \mathbf{Emp} = \qty{v \mid W_v = \varnothing} \), \( \mathbf{Fin} = \qty{v \mid W_v \text{ finite}} \), \( \mathbf{Inf} = \qty{v \mid W_v \text{ infinite}} \), \( \mathbf{Tot} = \qty{v \mid W_v = \mathbb W} \) are index sets.
	Note that the emptiness problem is precisely the index set \( \mathbf{Emp} \).
\end{example}
\begin{theorem}[Rice's theorem]
	No nontrivial index set is computable.
\end{theorem}
Fix \( w \in \mathbb W \) and consider the function
\[ g(u,v) = \begin{cases}
	f_{w,1}(v) & f_u(u) \downarrow \text{ or equivalently, } u \in \mathbb K \\
	\uparrow & \text{otherwise}
\end{cases} \]
This is computable, even though the case distinction itself is not computable.
By the \( s \)--\( m \)--\( n \) theorem, there is a total function \( h \) such that
\[ f_{h(u)}(v) = g(u,v) = \begin{cases}
	f_{w,1}(v) & u \in \mathbb K \\
	\uparrow & u \not\in \mathbb K
\end{cases} \]
If \( u \in \mathbb K \), then \( W_{h(u)} = W_w \).
If \( u \not\in \mathbb K \), then \( W_{h(u)} = \varnothing \).
This \( h \) will be used as a reduction function.
\begin{proof}
	Let \( I \) be an index set.
	Let \( e \) be such that \( W_e = \varnothing \).
	Then either \( e \in I \), or \( e \not\in I \).

	Suppose \( e \in I \).
	Since \( I \) is nontrivial, there exists \( w \not\in I \), so \( W_w \neq \varnothing \).
	Consider the function \( g \) from the discussion above, instantiated with this choice of \( w \), and apply the \( s \)--\( m \)--\( n \) theorem to obtain a total function \( h \).
	We claim that \( h \) reduces \( \mathbb W \setminus \mathbb K \) to \( I \).
	If \( u \in \mathbb K \), then \( W_{h(u)} = W_w \).
	Hence \( h(u) \sim w \), so \( h(u) \not\in I \).
	If \( u \not\in \mathbb K \), then \( W_{h(u)} = \varnothing \), so \( h(u) \sim e \), so \( h(u) \in I \).

	Now suppose \( e \not\in I \).
	Then there exists \( w \in I \), and \( W_w \neq \varnothing \).
	Take \( g \) and \( h \) as before.
	We claim now that \( h \) reduces \( \mathbb K \) to \( I \).
	If \( u \in \mathbb K \), then \( W_{h(u)} = W_w \), so \( h(u) \sim w \), so \( h(u) \in I \).
	If \( u \not\in \mathbb K \), then \( W_{h(u)} = \varnothing \), so \( h(u) \sim e \), giving \( h(u) \not\in I \).
\end{proof}
\begin{remark}
	The proof given for Rice's theorem shows a stronger statement: if \( e \in I \) then \( \mathbb W \setminus \mathbb K \leq_m I \), and if \( e \not\in I \) then \( \mathbb K \leq_m I \).
	This allows us to show that certain index sets are not computably enumerable.
	\( e \in \mathbf{Emp} \) so \( \mathbb W \setminus \mathbb K \leq_m \mathbf{Emp} \).
	Similarly, \( \mathbb W \setminus \mathbb K \leq_m \mathbf{Fin} \).
	For the other two index sets, we can only deduce that \( \mathbb K \leq_m \mathbf{Inf} \) and \( \mathbb K \leq_m \mathbf{Tot} \), since \( e \) does not lie in these sets.
\end{remark}
\begin{corollary}
	\( \mathbf{Emp}, \mathbf{Fin}, \mathbf{Inf}, \mathbf{Tot} \) are not computable.
\end{corollary}
\begin{corollary}
	The emptiness problem for type 0 grammars is unsolvable.
\end{corollary}
\begin{corollary}
	The equivalence problem for type 0 grammars is unsolvable.
\end{corollary}
\begin{proof}
	We define \( \mathbf{Eq} = \qty{(w, v) \mid W_w = W_v} \).
	The function \( g(w) = (w, e) \) can be performed by a register machine for any \( e \).
	If \( W_e = \varnothing \), then \( \chi_{\mathbf{Emp}} = \chi_{\mathbf{Eq}} \circ g \).
	Hence, if \( \mathbf{Eq} \) is computable, so is \( \mathbf{Emp} \).
\end{proof}
\begin{remark}
	One can show that \( \mathbf{Emp} \) is many-one equivalent to \( \mathbb W \setminus \mathbb K \), so it is \( \Pi_1 \)-complete, as proven on the last example sheet.
	The other problems \( \mathbf{Tot}, \mathbf{Inf}, \mathbf{Fin} \) are not in \( \Sigma_1 \) or \( \Pi_1 \).
\end{remark}
\begin{theorem}
	\( \mathbf{Fin} \) is not \( \Sigma_1 \) or \( \Pi_1 \).
\end{theorem}
\begin{proof}
	We know \( \mathbb W \setminus \mathbb K \leq_m \mathbf{Fin} \) by the proof of Rice's theorem, so \( \mathbf{Fin} \) is not \( \Sigma_1 \).
	To show it is not \( \Pi_1 \), one must show that \( \mathbb K \leq_m \mathbf{Fin} \).
	Consider
	\[ g(w,v) = \begin{cases}
		\uparrow & t_{w,1}(w,v) = a \\
		\varepsilon & \text{otherwise}
	\end{cases} \]
	Applying the \( s \)--\( m \)--\( n \) theorem, we obtain a total function \( h \) such that \( f_{h(w),1}(v) = g(w,v) \).
	We show \( h \) reduces \( \mathbb K \) to \( \mathbf{Fin} \).
	If \( w \in \mathbb K \), then \( f_{h(w),1} \) is undefined from \( v \) onwards, where \( v \) is the halting time of \( f_w(w) \).
	Hence, \( W_{h(w)} \) is finite, so \( h(w) \in \mathbf{Fin} \).
	If \( w \not\in \mathbb K \), then \( g(w,v) = \varepsilon \) for all \( v \).
	So \( f_{h(w),1} \) is the constant function with value \( \varepsilon \).
	Hence \( W_{h(w)} = \mathbb W \) which is infinite, so \( h(w) \not\in \mathbf{Fin} \).
\end{proof}
